In data processing systems it is frequently necessary to buffer or temporarily hold data being transferred within or outside of the system. The need to buffer data may arise because the receiver is busy when the data is transferred, or because the transfer rates of the transmitter and receiver are different. Whatever the reason, the data must be recovered from the buffer in the order it is transmitted. This process is known as first-in, first-out (FIFO).
FIFO memory devices typically have means to keep track of the status of the FIFO, namely, whether it is empty or full, and to generate signals when the FIFO is at the empty or full state. Such means may include write and read pointers and a comparator. The write pointer keeps track of the next location in the memory to be written to, and is incremented each time a data element is entered. The read pointer keeps track of the location in the memory where the last data element was read from and is incremented as data elements are read. The comparator basically determines when the pointers are equal or differ by a predetermined (constant) amount.
In addition to empty and full signals, some comparators also generate another signal indicating a predetermined amount of data has been stored in the buffer. For example, this other signal may be generated when the buffer is half full. This other signal is useful to maintain an efficient flow of data through the buffer. The aforementioned signal indicates when the buffer is filled to a predetermined level and may be used to indicate when the buffer should be read. This level may be optimized for a given system, but may be less than ideal for another system or for different operating conditions of the given system.
Another problem experienced by the means which track the amount of data in the FIFO is that the output signals--empty, full, etc.--are known to glitch or momentarily depart from their correct level due to nonuniform delays through binary counters and adders. To avoid such glitches the output signals are typically synchronized or only sampled after the outputs have stabilized. This requires the FIFO to be synchronized with the system clock.